package tree;

/**
 * 543. 二叉树的直径
 *
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
 * 这条路径可能穿过也可能不穿过根结点。
 * 注意：两结点之间的路径长度是以它们之间边的数目表示。
 *
 */
public class DiameterOfBinaryTree_543 {
    public int diameter = 1;

    // 至少右2个节点才存在直径
    public int diameterOfBinaryTree(TreeNode root) {
        recurse(root);
        return diameter - 1;
    }

    // 遍历每个节点，以每个节点为中心，计算其左右子树的的长度之和
    // 注意，此函数只返回以一个节点为中心，最长的一个子树的节点个数，而不是左右子树节点个数 之和
    public int recurse(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = recurse(root.left);
        int right = recurse(root.right);

        // 这里才是计算直径
        diameter = Math.max(diameter, left + right + 1);
        return Math.max(left, right) + 1;
    }

}
